The wide-spread acceptance and use of business and personal computers have spawned a renewed interest in the digital transmission of information. As a result, computer equipment and software are currently available for allowing the exchange of information between remotely located computers. This type of digital transmission can be accomplished by utilizing a standard voice-grade telephone line between the computers, and appropriate digital transmitters and receivers connected between the computers and the telephone lines. Such digital transmitters and receivers are currently available for providing the digital transmission and reception capabilities, and include, in many instances, provisions for error correction, detection and transmission line equalization to reduce and correct data transmission errors.
The voice-grade telephone line is generally used as the medium of digital transmission as it is widely available at almost any location, and is cost effective. However, because the voice-grade transmission line is essentially a pair of twisted wires, the bandwidth thereof imposes a severe restriction on the transmission rate of the digital signals. Currently, digital transmission rates of 2400 bits/second over such a line are possible, with an acceptable low error rate. For higher data transmission rates, the error rate increases to an objectionable level, primarily due to the bandlimiting characteristics of the line, as well as Gaussian noise which is superimposed on the digital signals.
Degradation of digital signals is due primarily to the bandlimiting characteristics of the transmission channel which tend to degrade the rise and fall times of the digital signals, thereby causing overlap between adjacent digital signals. When this overlap becomes significant, detectors in the receivers are unable to discriminate between the two signals. A detector error thus results, wherein the received data is tagged as being faulty and retransmission may become necessary. The same type of problems occur in digital receivers which receive free space digital transmission perturbated by signals reflected from objects. This is termed "multipath interference" and presents receiver decoding problems, in that the reflected transmissions are received a short time after the directed transmissions are received. Thus, the same signal is received by the receiver skewed in time and an erroneously decoded signal can result.
The noted problems with baseband transmissions at high data rates have been recognized, and attempts have been made to overcome the problems. For example, forward linear transversal equalizers have been integrated with digital receiver equipment in an attempt to compensate the lowpass transmission channel degradation. Matched filters are also customarily used for matching the transmission channel response o that of the digital receiver. However, while the forward linear transversal equalizer overcomes the lowpass filter problems to a certain degree, it also amplifies the Gaussian noise, and thus the noise problem becomes the predominant factor in faulty detection of the digital signals.
The linear equalizers were further improved by adding decisional feedback in an attempt to cancel the distortion caused by the lowpass filter effects of the transmission channel. Also, such equalizers were made adaptive to the transmission channel by adding a coefficient estimator which provides feedback to the matched filter and equalizer to produce dynamic corrections based upon time-varying changes of the channel or matched filter characteristics.
In 1974, it was theorized by Dr. Ungerboeck that a maximum-likelihood sequence estimation function was applicable to data transmission systems. G. Ungerboeck, "Adaptive Maximum-Likelihood Receiver For Carrier-Modulated Data-Transmission Systems", IEEE Transactions Communication, Vol. COM-22, pp. 624-636, May, 1974. The maximum-likelihood sequence estimation technique involves maximizing (or minimizing) an objective function. The objective function developed by Ungerboeck is too computational intensive to be of practical use. For this reason, Ungerboeck reformulated the problem in recursive form and employed the Viterbi algorithm to compute the estimate.
The Viterbi algorithm is a dynamic programming procedure. In its most general form, the Viterbi algorithm can be viewed as a solution to the problem of maximum aposteriori probability (MAP) estimation of the state of a finite-state, discrete-type Markov process observed in the presence of memoryless noise. In essence, the Viterbi algorithm determines the optimal path through a trellis structure, which defines all possible state transitions. The Viterbi algorithm significantly reduces the number of computations required to implement maximum-likelihood sequence estimation. A more detailed review of the Viterbi algorithm can be had by reference to "The Viterbi Algorithm", Proceedings of the IEEE. Vol. 61, No. 3, March, 1973, pp. 268-278, G. D. Forney, Jr.
As will be set forth in more detail below, the Viterbi algorithm involves a summation of a number of product terms which are carried out in an iterative sequence. Because the entire sequence of computations must be carried out for every digital bit transmitted, the time involved for each computation usually limits the transmission rate to about 2400 bits/second. Even high speed signal processors are not able to increase the computational speed sufficiently to significantly increase the data transmission rate.
Yet another approach has been taken to reduce the computational complexity of the Viterbi algorithm by reducing the transmission channel memory. Transmission channel memory is an inherent characteristic of time-varying channels, in which the channel response to a particular signal may depend on the occurrence or non-occurrence of a prior signal. It is well known that with reduced channel memory, the number of computations involved in the Viterbi algorithm can also be reduced. Attempts to reduce the channel memory typically involve pre-filtering of the input signals to reduce the speed of the digital pulses. This approach, however, is suboptimal in nature as it increases the channel noise, thereby also decreasing the signal-to-noise ratio of the received signal. Attempts have also been made to reduce the number of states in the maximum-likelihood sequence estimation trellis structure which has the effect of reducing the channel memory. This alternative is also suboptimal in nature, as a trellis structure with fewer states than required, even though such states are seldomly encountered, increases the error rate of the receiver.
From the foregoing, it can be seen that those skilled in the art have recognized the importance of basebanded digital transmission systems and have also recognized the attendant problems. Also, it is apparent that there is a constant effort, and no small effort, to improve the performance of baseband digital transmission systems such that increased transmission rates are possible. A need thus exists for a new method and structure which can compute the maximum-likelihood sequence estimation faster than the Viterbi algorithm implementaion. To avoid increasing the error rate, the new method and structure should preferably implement the maximum-likelihood sequence estimation optimally.